PART A
Mr. Snowman, the mayor of Little Gotham, faces a serious snow storm in the coming days. He has two snow removal machines, and needs to remove snow from three different roads. He has 24 hours to remove 15 inches of snow from Road 1, 24 inches of snow from Road 2, and 18 inches of snow from Road 3. (Unusual for different amounts of snow to have to be removed from different roads, but that is the problem that Mr. Snowman faces.) In addition, each machine removes snow at a different rate on the three roads.
Machine 1 can remove one inch an hour from Road 1; it removes 1.2 inches an hour from Road 2; it removes two inches an hour from Road 3. Machine 2 can remove two inches an hour from Road 1, three inches an hour from Road 2 and three inches an hour from Road 3. The optimization problem is to remove as much snow as possible in 24 hours using the two machines.
The decision variables are:
Mr. Snowman tries to model it as a linear program. He gives the following formulation. As his assistant, you are concerned that some of the inequalities have been reversed. Which of the following is the best response?
$$ \left. \begin{array}{rrcl} & \max x_{11} + 2x_{12} + 1.2x_{21} + 3x_{22} + 2x_{31} +3x_{32} & & \\ \text {s.t.:} & & & \\ (1)& x_{11} + x_{21} + x_{31} & \le & 24 \\ (2)& x_{12} + x_{22} + x_{32} & \le & 24 \\ (3)& x_{11} + 2x_{12} & \le & 15 \\ (4)& 1.2x_{21} + 3x_{22} & \le & 24 \\ (5)& 2x_{31} + 3x_{32} & \le & 18 \\ (6)& x_{11}, x_{12}, x_{21}, x_{22}, x_{31}, x_{32}, & \ge & 0 \\ \end{array}\right\} $$
In [1]:
using JuMP
#Define model
MaxIce = Model()
#Non-negativity
@variable(MaxIce, x[1:3,1:2] >= 0 )
#Time Constraint
@constraint(MaxIce, x[1,1] + x[2,1] + x[3,1] <= 24)
@constraint(MaxIce, x[1,2] + x[2,2] + x[3,2] <= 24)
#The amount of ice in each each road
@constraint(MaxIce, x[1,1] + 2x[1,2] <= 15)
@constraint(MaxIce, 1.2x[2,1] + 3x[2,2] <= 24)
@constraint(MaxIce, 2x[3,1] + 3x[3,2] <= 18)
# Maximize the amount of ice removed
@objective(MaxIce, Max, 1x[1,1] + 1.2x[2,1] + 2x[3,1] + 2x[1,2] + 3x[2,2] + 3x[3,2])
#Solve the optimization problem
solve(MaxIce)
#Determine consumption amounts
println("Operation time of Machine 1: ", getvalue(x[1,1] + x[2,1] + x[3,1]))
println("Operation time of Machine 2: ", getvalue(x[1,2] + x[2,2] + x[3,2]))
#Determine optimal amount of ice removed
println("Optimal amount of ice removed: ", getobjectivevalue(MaxIce))
PART B
Consider now that the mayor wants to remove the snow as soon as possible.
Hint: Let $z$ be the earliest time that machines $m_1$ and $m_2$ have both finished. The objective is to minimize $z$.
Mr. Snowman tries to model it as a linear program. He gives the following formulation. As his assistant, you are concerned that some of the inequalities have been reversed. Which of the following is the best response?
$$ \left. \begin{array}{rrcl} & \min z & & \\ \text {s.t.:} & & & \\ (1)& x_{11} + x_{21} + x_{31} & \le & z\\ (2)& x_{12} + x_{22} + x_{32} & \le & z\\ (3)& x_{11} + 2x_{12} & = & 15 \\ (4)& 1.2x_{21} + 3x_{22} & = & 24 \\ (5)& 2x_{31} + 3x_{32} & = & 18 \\ (6)& x_{11}, x_{12}, x_{21}, x_{22}, x_{31}, x_{32}, z & \ge & 0 \\ \end{array} \right\} $$
In [2]:
using JuMP
#Define model
MinTime = Model()
#Non-negativity
@variable(MinTime, x[1:3,1:2] >= 0 )
@variable(MinTime, z >= 0)
# We have find the minimum of the maximum
@constraint(MinTime, x[1,1] + x[2,1] + x[3,1] <= z)
@constraint(MinTime, x[1,2] + x[2,2] + x[3,2] <= z)
#The amount of ice in each each road
@constraint(MinTime, x[1,1] + 2x[1,2] == 15)
@constraint(MinTime, 1.2x[2,1] + 3x[2,2] == 24)
@constraint(MinTime, 2x[3,1] + 3x[3,2] == 18)
# Minimize the amount of ice removed
@objective(MinTime, Min, z)
#Solve the optimization problem
solve(MinTime)
#Determine consumption amounts
println("variable values: ", getvalue(x))
#Determine optimal amount of ice removed
println("Optimal amount of time used by both machine: ", getobjectivevalue(MinTime))